1.1. Field of the Invention
This invention relates to cryptographic communication in general, and more specifically, to methods and apparatus for securely proving knowledge of a shared small secret password between two parties using messages exchanged across an open communication channel.
1.2. Description of the Related Art
Passwords are an essential component of secure systems. Although they play a crucial role in authenticating the identity of people to systems, traditional password-based network authentication systems have weaknesses due to improper use of passwords. Such systems often use the password as if it were a cryptographic key, and require the password to be chosen as carefully as one would choose a cryptographic key. One requirement is that the choice be from an effectively large "password-space". The size of this space is sometimes expressed in terms of a number of bits of "entropy". For simplicity, we often refer to any low-entropy secret from a space that is vulnerable to dictionary attacks as a "small password". In practice, due to human limitations, many passwords are small. This is a problem for many systems which can be attacked using a repeated computation using all possible (or likely) guesses for the password. This is known as a brute-force, or dictionary attack.
Dictionary attacks can occur on-line, in an interaction between an attacker and a legitimate user or system. They can also occur off-line, using information gathered by monitoring messages sent between two legitimate parties during an authentication protocol exchange. On-line attacks can often be easily detected and thwarted, by counting bad attempts and denying access. Banking ATM machines thwart attack by retaining the user's card after three bad access attempts. But remote authentication opens the possibility of an off-line attack on the messages transmitted across a network.
As widely available computing power increases, successful off-line dictionary attacks on a small password become easier. Today, ever-increasing computer power has clearly outpaced the (unchanging) ability of people to remember longer passwords. Today, 56-bit symmetric key seem to offer only marginal security. U.S. export regulations have allowed export of 40-bit key systems, presumably because they are breakable. Thus, in many systems, a "safely large password" requires more than 40 bits of entropy, and the number is steadily growing. On the other hand, it seems that many people cannot easily remember and use a password from a space of 32 bits. This is equivalent to a random 10 digit number, about 6 random letters and digits, or a pair of words from an average English dictionary. Several studies over many years have found that a significant percentage of user-chosen passwords can be found with a modest computational effort, having an effective size of less than 30 bits (roughly a billion choices). At one extreme, bank-card PIN numbers have less than 14 bits. Forcing everyone to double or triple the size of their passwords, and expecting them to not write them down, or expecting most people to be comfortable using "pass-phrases", is denying the inevitable truth. People can't or won't properly handle anything larger than a small password, so systems must protect them from attack. In light of this, most traditional network authentication systems that use passwords are obsolete. Better systems must be designed and deployed that are resistant to off-line dictionary attack, to safely tolerate the use of potentially small passwords.
1.3. Detailed Objective
Our goal is to authenticate one party to the other with a series of messages exchanged across an open network, where interception or modification of the messages by an untrusted third party may be possible. Furthermore, we do not require that either party have access to any additional long-lived keys for either a symmetric or a public-key encryption system--we seek a method based solely on the password. In light of the crucial role of the password, we must protect it as much as possible.
These methods can be used for direct person-to-person authentication, where an appropriate computer or device performs the required protocol computation on behalf of the person. More typically, one of the parties is a host computer. We will refer to the user's computer as "Alice" and the host computer as "Bob".
We assume that Alice and Bob use a small password as the basis for establishing a secure communication channel between the them, and we assume that an attacker has the computational power to enumerate all possible password values to attempt a dictionary attack. We first desire a method where Alice and Bob prove to each other that they know the same secret. We also desire an extended method where Bob, who only has knowledge of a "hidden-password", verifies that Alice knows the password. The hidden-password in our extended method will be a specially constructed one-way transformation of the password.
Historically, much attention has focused on the problem of getting Alice to use a large "well-chosen" password. Newer research, such as ours, focuses attention on how to legitimately use a small password for remote authentication across an open insecure network. This must be done without making the password vulnerable to off-line dictionary attack. A related goal of our methods is to provide a zero-knowledge password proof. One party proves knowledge of the password to the another without revealing the password in the process. The importance of the zero-knowledge characteristic is explained further below.
1.4. Traditional methods
Most older methods of remote authentication based on a shared secret do not survive dictionary attacks when the secret is small. In a common example, Alice sends a random number R to Bob, Bob computes a one-way collision-free hash function h of both R and the password S, and sends the result h(R,S) to Alice. Alice also computes h(R,S) and compares it to Bob's result. If they are equal, Bob has proven knowledge of the password to Alice, and because of the hash, the secret password is not directly revealed to a third party who monitors the exchange. The randomness of R prevents replay attacks. However, when the password is small, Eve, an eavesdropper who obtains R and h(R,S), can repeatedly hash each possible password S' in the dictionary with R, and compare each result h(R,S') to Bob's response. (The dictionary entries may be either pre-built, or computed as needed.) When a match is found, the attacker knows that S' is the password.
When tolerance for small passwords is added to all the classic requirements for a secure exchange, most traditional password authentication methods are shown to be obsolete.
Some methods can confirm knowledge of a small shared secret based on the parties' access to other long-lived data. This data may be a large shared secret, or a large public key. There are many general methods for public-key-based authentication. Such schemes pose additional problems such as certifying public-keys, requiring a secure key distribution system, or requiring secure storage for large secret keys. Here we seek methods that are based solely on an easily-memorized secret.
A common approach to protecting the password uses persistent public keys. Typically a client Alice sends a password to a server Bob where he then uses the clear-text password for verification. But before sending it, Alice first seals the password in an encrypted message using Bob's public key. While this approach is intended to provide assurance that only the holder of the corresponding private key, presumably Bob, can unseal the message and discover the password, it creates a new set of security issues.
In many systems, such as the common web browser using Secure Sockets Layer (SSL), there are several ways that an invalid server Barry can be mistaken for Bob such that an unwary user might reveal the password to the wrong party. The security of these systems may depend on:
Bob keeping the private key secret, PA1 Alice knowing or recognizing Bob's exact name, PA1 the validity of any certificates that bind "Bob" to the public key, PA1 the integrity of the chain of certification authorities, PA1 Alice verifying that she's really connected to "Bob", and/or PA1 Alice verifying that SSL security is in fact enabled. PA1 g and p are well-known numbers, where g is a primitive root of p. PA1 Bob chooses a random R.sub.B, computes Q.sub.B =g.sup.R.sup..sub.B mod p, and sends Q.sub.B to Alice. PA1 Alice chooses a random R.sub.A, computes Q.sub.A =g.sup.R.sup..sub.A mod p, and send Q.sub.A to Bob. PA1 Bob computes K=Q.sub.A.sup.R.sup..sub.B mod p. PA1 Alice computes K=Q.sub.B.sup.R.sup..sub.A mod p. PA1 V is an ephemeral public key. PA1 {m}v is a message m sealed with V. PA1 Ep(m) is a message m symmetrically encrypted using a key derived from password P. PA1 K is the resulting password-authenticated key distributed by the method. PA1 x,y,z are random numbers. PA1 PK-EKE PA1 DH-EKE PA1 A.fwdarw.B: E.sub.p (g.sup.x) PA1 Gong, et. al.
The user may connect through an SSL-enabled channel to the wrong server, perhaps due to a redirected URL that isn't noticed by the user. Or the user may be tricked into using a connection that isn't protected by SSL at all, due to a misleading insecure web page. Another problem is where the user has multiple passwords for different servers, and makes the mistake of sending a highly sensitive password to a relatively untrusted server. In any case, the practice of sending the password directly to the server creates unnecessary risk.
The problem where Barry poses as Bob is a general issue with public key sealing systems, which must first perfectly establish identity in order to perform a safe pass-through authentication. Any cause for identity confusion can let Barry get a password that was intended for Bob. Even when a challenge/hashed-response method is performed through an server-sealed channel, Barry may still get a chance to "crack" the password. A zero-knowledge password proof completely eliminates these risks by not revealing the password to anyone during the verification process.
1.5. Minimal Disclosure Methods
A few methods exist that address our goal of preventing off-line dictionary attacks, without requiring access to additional long-lived keys. Examples are the various Encrypted Key Exchange (EKE) methods described by Bellovin & Merritt [BM92] and the "secret public-key" methods described by Gong and others in [GLSN93, Gon95]. An example of an enhancement where Bob stores a one-way function of the password, and verifies that Alice knows the original password, are the A-EKE methods described in [BM94]. These documents are herein incorporated by reference. These methods represent the best of the prior art, and reveal little or no information for an attacker to mount a dictionary attack. We will call these "minimal disclosure" methods, since they minimize disclosure of information about the password to potential attackers.
Another method that is somewhat resistant to passive dictionary attack is called Fortified Key Negotiation (FKN), and is described in [AL94] We refer to this as a "reduced disclosure" method, since it may leak a considerable amount of information.
When properly constructed, a minimal disclosure method performs the function of a zero-knowledge password proof. The proof is zero-knowledge in the sense that no unnecessary information about the password is revealed during the process of password verification. Each party gets one chance to verify the password in each run of the protocol, and eavesdroppers get no information to help verify their guesses.
Of course, an attacker posing as one of the parties always has the opportunity to test one guess for the password during each run of the protocol, but there is no subsequent opportunity to verify unlimited guesses off-line.
1.6. Diffie-Hellman Exponential Key Exchange
A common function used in modem cryptographic methods is the Diffie-Hellman exponential key exchange ("DH") described in [DH79]. This is an example of a public-key distribution system, the purpose of which is to distribute keys to one or more parties using some kind of public-key technique. This is different than a public-key cryptosystem the purpose of which is to typically perform signing and/or sealing operations.
The major limitation of original DH is that it is an unauthenticated public-key exchange--It doesn't prove the identity of either party to the other. It is thus vulnerable to a "man-in-the-middle" attack where a third party, Mallory, performs two distinct DH exchanges with Alice and Bob to create separate encrypted channels. By decrypting and re-encrypting all messages passed between Alice and Bob, Mallory can act as an undetected eavesdropper. Despite this limitation, DH has important uses and the basic computation in DH forms a basis for many well-known security schemes, such as the ElGamal and related public-key crypto-systems, the DSS digital signature standard [NIST94]. Two methods that have incorporated DH to provide an authenticated key exchange are the Station-to-Station protocol and DH-EKE, one of the Encrypted Key Exchange methods. Our methods will also utilize a DH exchange.
The general construction of DH uses exponentiation within a mathematical group. Although a variety of groups can be used in DH, a common example uses arithmetic in Z.sub.p *, the multiplicative group of the Galois field of integers modulo p, where p is a large prime. Z.sub.p * is also sometimes written as GF(p)*. The elements (members) of this group are the integers from 1 to p-1, and the group operator (represented by *) is multiplication modulo p. We review the classic DH operation here:
The result of the exchange is that both Alice and Bob alone share knowledge of a large key K. They both compute the same value of K because (g.sup.R.sup..sub.A ).sup.R.sup..sub.B mod p=(g.sup.R.sup..sub.B ).sup.R.sup..sub.A mod p.
DH can also use other groups, including large prime-order subgroups of Z.sub.p *, and groups of points on elliptic curves over finite fields. The principal advantage of alternate groups such as elliptic curves lies in their increased resistance to a discrete-log computation for a given computational cost, assuming the current knowledge of discrete log techniques. With elliptic curve groups, the size of the field can be much smaller than the size required with Z.sub.p *, and thus fewer bits are needed to represent the group elements.
We will use the term "exponentiation" to broadly refer to repeated applications of the group operator on an element with itself. In some cases, the group operator does not use exponential arithmetic in the integers. For example, the literature on elliptic curve groups traditionally describes the group operator for two points as "addition" of points, and group exponentiation to an integer power is described as "multiplication of a point by an integer". Further description of elliptic curve groups can be found in [P1363].
Though our discussion will focus on Z.sub.p * and it's subgroups, the techniques we will discuss apply to use of DH in any other suitable group with comparable structure. We now briefly review some algebraic results that are relevant to use of the DH in both our method as well as in DH-EKE.
1.7. Selection of DH Parameters g and p, and the Structure of Z.sub.p *
The first DH computation (using Z.sub.p *) is g.sup.R mod p, where g and p are specially chosen, and R is a large random number. Proper selection of g and p is crucial to the DH exponential key exchange, in general, and even more so in password-authenticated DH methods. We will generally limit our discussion to groups where the factorization of p-1 is known, and where p-1 has a large prime factor q. A large prime factor prevents easy solutions to the discrete logarithm problem, and methods to generate such values of p with several hundreds and even thousands of bits are well known to those skilled in the art. It has been recommended that the sizes of R and q be at least twice the number of bits needed in the resulting key. The size of p must generally be much larger resist long-term attack on discrete logs in Z.sub.p *.
Throughout the discussion we use the abbreviated notation "x.sup.z " to mean exponentiation within some DH group. With respect to Z.sub.p *, "x.sup.z " is equivalent to (x raised to the power z) mod p". We will also refer to subgroups of Z.sub.p * as G.sub.x, where x is the order of the group.
The literature [PH78, McC90] discusses the proper selection of g and p, in particular to address the concern that easier solutions to the discrete logarithm problem make it easier to attack DH. Classical values for p and g in DH are where p=2q+1, q is also a large prime, and g is a primitive root of p. It has also been recommended to use values for g in DH that are generators of a smaller but still large subgroup of Z.sub.p * [P1363]. However, the available literature does not discuss how the structure of the group is particularly relevant to authentication systems that use DH. We explore this further in the detailed description of our invention.
In both [BM92] and [STW95] we find some analysis of the security of DH-EKE. [BM92] warns against allowing 0 to be used as an exponent. Attacks using other special numbers were, at that time, unknown. A variation of DH-EKE named M-EKE and general techniques for refining and strengthening the protocol against certain attacks are discussed in [STW95]. In the course of our invention, we uncovered a flaw in DH-EKE as described in the available literature. An analysis of this flaw and a means for correcting it are included in our method.
All zero-knowledge password methods in the prior art use some kind of public key distribution method to establish a large shared key, where each method achieves the minimal disclosure objective by using a password-derived symmetric key to encrypt key distribution messages in both directions. A brief review of three methods is shown here in a common notation, highlighting the messages used for key distribution and omitting the key verification phase.
A.fwdarw.B: E.sub.p (V) PA2 B.fwdarw.A: E.sub.p ({K}v) PA2 B.fwdarw.A: E.sub.p (g.sup.y) PA2 A.fwdarw.B: E.sub.p (V, x) PA2 B.fwdarw.A: {y, E.sub.p (z)}.sub.v
K=g.sup.xy PA3 K=hash(x, y)
We note that in each of these methods at least one of the parties encrypts a public key using a password-derived key such that the other party must decrypt it, and password-based encryption is used in messages in both directions. While the prior art suggests that one of the two encryption steps of the public keys in DH-EKE may be omitted, no prior art reference shows how to do this while still achieving our objectives.
One reason why it is desirable to reduce the use of the password as a symmetric key is to remove the risk of exposing the password to a verifiable plain-text attack. Complex constraints in prior methods, such as the carefully-designed modulus in [BM92], have been introduced to address this risk. Our disclosure shows novel ways to eliminate the need for using password-based symmetric encryption of the messages in one or both directions. Some of our methods use no symmetric function at all, which makes them simpler and easier to implement than prior methods. We also hope that our improvements will simplify the effort to prove the security of these schemes.